/*
 * Copyright (c) 2003, the JUNG Project and the Regents of the University 
 * of California
 * All rights reserved.
 *
 * This software is open-source under the BSD license; see either
 * "license.txt" or
 * http://jung.sourceforge.net/license.txt for a description.
 */
/*
 * 
 * Created on Oct 29, 2003
 */
package edu.uci.ics.jung.algorithms.util;

import java.util.AbstractCollection;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.Vector;

import org.apache.commons.collections15.IteratorUtils;

/**
 * An array-based binary heap implementation of a priority queue, which also
 * provides efficient <code>update()</code> and <code>contains</code>
 * operations. It contains extra infrastructure (a hash table) to keep track of
 * the position of each element in the array; thus, if the key value of an
 * element changes, it may be "resubmitted" to the heap via <code>update</code>
 * so that the heap can reposition it efficiently, as necessary.
 * 
 * @author Joshua O'Madadhain
 */
public class MapBinaryHeap<T> extends AbstractCollection<T>
		implements Queue<T> {
	private Vector<T> heap = new Vector<T>(); // holds the heap as an implicit
												// binary tree
	private Map<T, Integer> object_indices = new HashMap<T, Integer>(); // maps
																		// each
																		// object
																		// in
																		// the
																		// heap
																		// to
																		// its
																		// index
																		// in
																		// the
																		// heap
	private Comparator<T> comp;
	private final static int TOP = 0; // the index of the top of the heap

	/**
	 * Creates a <code>MapBinaryHeap</code> whose heap ordering is based on the
	 * ordering of the elements specified by <code>c</code>.
	 */
	public MapBinaryHeap(Comparator<T> comp) {
		initialize(comp);
	}

	/**
	 * Creates a <code>MapBinaryHeap</code> whose heap ordering will be based on
	 * the <i>natural ordering</i> of the elements, which must be
	 * <code>Comparable</code>.
	 */
	public MapBinaryHeap() {
		initialize(new ComparableComparator());
	}

	/**
	 * Creates a <code>MapBinaryHeap</code> based on the specified collection
	 * whose heap ordering will be based on the <i>natural ordering</i> of the
	 * elements, which must be <code>Comparable</code>.
	 */
	public MapBinaryHeap(Collection<T> c) {
		this();
		addAll(c);
	}

	/**
	 * Creates a <code>MapBinaryHeap</code> based on the specified collection
	 * whose heap ordering is based on the ordering of the elements specified by
	 * <code>c</code>.
	 */
	public MapBinaryHeap(Collection<T> c, Comparator<T> comp) {
		this(comp);
		addAll(c);
	}

	private void initialize(Comparator<T> comp) {
		this.comp = comp;
		clear();
	}

	/**
	 * @see Collection#clear()
	 */
	@Override
	public void clear() {
		object_indices.clear();
		heap.clear();
	}

	/**
	 * Inserts <code>o</code> into this collection.
	 */
	@Override
	public boolean add(T o) {
		int i = heap.size(); // index 1 past the end of the heap
		heap.setSize(i + 1);
		percolateUp(i, o);
		return true;
	}

	/**
	 * Returns <code>true</code> if this collection contains no elements, and
	 * <code>false</code> otherwise.
	 */
	@Override
	public boolean isEmpty() {
		return heap.isEmpty();
	}

	/**
	 * Returns the element at the top of the heap; does not alter the heap.
	 */
	@Override
	public T peek() {
		if (heap.size() > 0) {
			return heap.elementAt(TOP);
		}
		return null;
	}

	/**
	 * Returns the size of this heap.
	 */
	@Override
	public int size() {
		return heap.size();
	}

	/**
	 * Informs the heap that this object's internal key value has been updated,
	 * and that its place in the heap may need to be shifted (up or down).
	 * 
	 * @param o
	 */
	public void update(T o) {
		// Since we don't know whether the key value increased or
		// decreased, we just percolate up followed by percolating down;
		// one of the two will have no effect.

		int cur = object_indices.get(o).intValue(); // current index
		int new_idx = percolateUp(cur, o);
		percolateDown(new_idx);
	}

	/**
	 * @see Collection#contains(java.lang.Object)
	 */
	@Override
	public boolean contains(Object o) {
		return object_indices.containsKey(o);
	}

	/**
	 * Moves the element at position <code>cur</code> closer to the bottom of
	 * the heap, or returns if no further motion is necessary. Calls itself
	 * recursively if further motion is possible.
	 */
	private void percolateDown(int cur) {
		int left = lChild(cur);
		int right = rChild(cur);
		int smallest;

		if ((left < heap.size()) && (comp.compare(heap.elementAt(left),
				heap.elementAt(cur)) < 0)) {
			smallest = left;
		} else {
			smallest = cur;
		}

		if ((right < heap.size()) && (comp.compare(heap.elementAt(right),
				heap.elementAt(smallest)) < 0)) {
			smallest = right;
		}

		if (cur != smallest) {
			swap(cur, smallest);
			percolateDown(smallest);
		}
	}

	/**
	 * Moves the element <code>o</code> at position <code>cur</code> as high as
	 * it can go in the heap. Returns the new position of the element in the
	 * heap.
	 */
	private int percolateUp(int cur, T o) {
		int i = cur;

		while ((i > TOP) && (comp.compare(heap.elementAt(parent(i)), o) > 0)) {
			T parentElt = heap.elementAt(parent(i));
			heap.setElementAt(parentElt, i);
			object_indices.put(parentElt, Integer.valueOf(i)); // reset index to
																// i
															// (new location)
			i = parent(i);
		}

		// place object in heap at appropriate place
		object_indices.put(o, Integer.valueOf(i));
		heap.setElementAt(o, i);

		return i;
	}

	/**
	 * Returns the index of the left child of the element at index
	 * <code>i</code> of the heap.
	 * 
	 * @param i
	 * @return the index of the left child of the element at index
	 *         <code>i</code> of the heap
	 */
	private static int lChild(int i) {
		return (i << 1) + 1;
	}

	/**
	 * Returns the index of the right child of the element at index
	 * <code>i</code> of the heap.
	 * 
	 * @param i
	 * @return the index of the right child of the element at index
	 *         <code>i</code> of the heap
	 */
	private static int rChild(int i) {
		return (i << 1) + 2;
	}

	/**
	 * Returns the index of the parent of the element at index <code>i</code> of
	 * the heap.
	 * 
	 * @param i
	 * @return the index of the parent of the element at index i of the heap
	 */
	private static int parent(int i) {
		return (i - 1) >> 1;
	}

	/**
	 * Swaps the positions of the elements at indices <code>i</code> and
	 * <code>j</code> of the heap.
	 * 
	 * @param i
	 * @param j
	 */
	private void swap(int i, int j) {
		T iElt = heap.elementAt(i);
		T jElt = heap.elementAt(j);

		heap.setElementAt(jElt, i);
		object_indices.put(jElt, Integer.valueOf(i));

		heap.setElementAt(iElt, j);
		object_indices.put(iElt, Integer.valueOf(j));
	}

	/**
	 * Comparator used if none is specified in the constructor.
	 * 
	 * @author Joshua O'Madadhain
	 */
	private class ComparableComparator implements Comparator<T> {
		/**
		 * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
		 */
		@Override
		@SuppressWarnings("unchecked")
		public int compare(T arg0, T arg1) {
			if (!(arg0 instanceof Comparable) || !(arg1 instanceof Comparable)) {
				throw new IllegalArgumentException(
						"Arguments must be Comparable");
			}

			return ((Comparable<T>) arg0).compareTo(arg1);
		}
	}

	/**
	 * Returns an <code>Iterator</code> that does not support modification of
	 * the heap.
	 */
	@Override
	public Iterator<T> iterator() {
		return IteratorUtils.<T> unmodifiableIterator(heap.iterator());
	}

	/**
	 * This data structure does not support the removal of arbitrary elements.
	 */
	@Override
	public boolean remove(Object o) {
		throw new UnsupportedOperationException();
	}

	/**
	 * This data structure does not support the removal of arbitrary elements.
	 */
	@Override
	public boolean removeAll(Collection<?> c) {
		throw new UnsupportedOperationException();
	}

	/**
	 * This data structure does not support the removal of arbitrary elements.
	 */
	@Override
	public boolean retainAll(Collection<?> c) {
		throw new UnsupportedOperationException();
	}

	@Override
	public T element() throws NoSuchElementException {
		T top = this.peek();
		if (top == null) {
			throw new NoSuchElementException();
		}
		return top;
	}

	@Override
	public boolean offer(T o) {
		return add(o);
	}

	@Override
	public T poll() {
		T top = this.peek();
		if (top != null) {
			T bottom_elt = heap.lastElement();
			heap.setElementAt(bottom_elt, TOP);
			object_indices.put(bottom_elt, Integer.valueOf(TOP));

			heap.setSize(heap.size() - 1); // remove the last element
			if (heap.size() > 1) {
				percolateDown(TOP);
			}

			object_indices.remove(top);
		}
		return top;
	}

	@Override
	public T remove() {
		T top = this.poll();
		if (top == null) {
			throw new NoSuchElementException();
		}
		return top;
	}

}
